package day39;

// 最长公共子序列
// 动归问题：相等++ 不相等就取max并结束


// 经参考：
import java.util.Scanner;

public class Main2 {
    // 最长公共子序列数目
    private static int maxLen(String str1, String str2) {
        int len1 = str1.length();
        int len2 = str2.length();
        int[][] dp = new int[len1+1][len2+1];
        for (int i = 1; i <= len1; i++) { // 注意始末
            for (int j = 1; j <= len2; j++) {
                if(str1.charAt(i-1) == str2.charAt(j-1)) {
                    dp[i][j] = dp[i-1][j-1] +1;
                } else {
                    dp[i][j] = dp[i-1][j]>dp[i][j-1] ? dp[i-1][j]:dp[i][j-1];
                }
            }
        }
        return dp[len1][len2];
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            String str1 = in.next();
            String str2 = in.next();
            int len =maxLen(str1,str2);
            System.out.println(len);
        }
    }
}
